import unittest
import random


symbols = [
    list(')'),
    list('*/'),
    list('+-'),
    list('(')
]
priority = [(sym, i) for i, ls in enumerate(symbols) for sym in ls]

symbols = [x for ls in symbols for x in ls]
priority = dict(priority)


class Stack:
    def __init__(self):
        self._list = []

    def __len__(self):
        return len(self._list)
    
    def push(self, e):
        self._list.append(e)

    def pop(self):
        return self._list.pop(-1)

    def peek(self):
        """Return the last element of stack"""
        return self._list[-1]

    @property
    def is_empty(self):
        return [False, True][self._list == []]



def sym_gt(s1, s2):
    """"compare whether s1 is greater than s2 (has higher priority)"""
    try:
        p1 = priority[s1]
        p2 = priority[s2]
    except KeyError:
        raise KeyError('Unknown symbol')

    # the smaller the index, the higher the priority
    if p1 < p2:
        return True
    return False


def sym_eq(s1, s2):
    try:
        p1 = priority[s1]
        p2 = priority[s2]
    except KeyError:
        raise KeyError('Unknown symbol')

    if p1 == p2:
        return True
    return False


def split_expr(s):
    """Split a string into a collection of digits and symbols"""
    items = []
    digits = []  # characters
    
    i = 0
    length = len(s)
    while i < length:
        if s[i].isdigit():
            # deal with negative numbers
            if i > 1 and items[-1] == '-' and items[-2] in symbols:
                digits.append(items.pop())
            elif i == 1 and items[-1] == '-':
                digits.append(items.pop())

            # to accumulate the digits
            while i < length and s[i].isdigit():
                digits.append(s[i])
                i += 1
            
            item = ''.join(digits)
            items.append(float(item))
            digits = []
            continue
            
        elif s[i] in symbols:
            items.append(s[i])
        i += 1

    print('split: ', items)
    return items


def mid2suff(expression):
    """
    mid2suff(expression: list) -> list
    Translate the midfix expression into suffix expression

    examples:
    3 - 1 + 2  # continuous same priority
    """
    sk = Stack()
    out = []
    
    for x in expression:
        if isinstance(x, (int, float)):
            out.append(x)
        elif not sk.is_empty:
            if x == ')' or sym_gt(sk.peek(), x):
                for i in range(len(sk)):
                    out.append(sk.pop())

                if x != ')':  # does not push bracket into stack
                    sk.push(x)

            elif sym_eq(sk.peek(), x):
                out.append(sk.pop())
                sk.push(x)

            else:
                sk.push(x)
        else:
                sk.push(x)

    # clear the remains
    for i in range(len(sk)):
        out.append(sk.pop())

    return out


def evaluate(expression):
    """Evaluate a suffix expression"""
    sk = Stack()

    for x in expression:
        if isinstance(x, (int, float)):
            sk.push(float(x))
        else:
            num2 = sk.pop()
            num1 = sk.pop()
            temp = operations[x](num1, num2)
            sk.push(temp)

    return sk.peek()


def add(x1, x2):
    return x1 + x2


def substract(x1, x2):
    return x1 - x2


def multiply(x1, x2):
    return x1 * x2


def divide(x1, x2):
    return x1 / x2


operations = {
    "+": add,
    "-": substract,
    "*": multiply,
    "/": divide
}



# ===== ===== ===== ===== =====
# Tests
# ===== ===== ===== ===== =====
class MyTest(unittest.TestCase):
    
    def gen_expr(self, n_num=5, min_num=-10, max_num=10):
        sym_set = symbols.copy()
        sym_set.remove('(')
        sym_set.remove(')')
        chars = []

        for i in range(n_num):
            num = random.randrange(min_num, max_num)
            sym = random.choice(sym_set)
            chars.append(num)
            chars.append(sym)
        chars.pop()

        return chars

    def ttest_gen_expr(self):
        for i in range(5):
            self.gen_expr()

    def ttest_split_expr(self):
        for i in range(10):
            chars = self.gen_expr()
            rslt1 = split_expr(''.join(chars))
            rslt2 = split_expr(' '.join(chars))

            self.assertEqual(chars, rslt1)
            self.assertEqual(chars, rslt2)

    def test_evaluate_pipeline(self):
        print("\n\n\n\n\ntesting pipeline...")
        exprs = [[-3, '/', 9, '-', 5, '+', -9, '-', -1],
                 [4, '+', 6, '*', 5, '/', -10, '*', -4]]
        for i in range(1000):
            expr = self.gen_expr(n_num=10)
            exprs.append(expr)

        for expr in exprs:
            suff = mid2suff(expr)
            
            expr = [str(x) for x in expr]
            expr = ' '.join(expr)

            # print('testing: ', expr)
            # print('suff: ', suff)
            try:
                self.assertEqual(eval(expr), evaluate(suff))
            except ZeroDivisionError:
                # print("zero division")
                pass


if __name__ == '__main__':
    unittest.main()


